
def quick_sort(alist,start,end):
    """快速排序
    将数据分为两部分，一部分比另外一部分都要小，然后递归
    """
    if start>=end:
        return


    # base_cur = start
    base_data = alist[start]
    left_cur = start
    right_cur = end

    while left_cur<right_cur:
        while alist[right_cur] >= base_data and left_cur<right_cur:
            right_cur -= 1
        alist[left_cur] = alist[right_cur]

        while alist[left_cur] <  base_data and left_cur<right_cur:
            left_cur += 1
        alist[right_cur] = alist[left_cur]

    alist[left_cur] = base_data
    # print(base_data)
    # print(left_cur,right_cur)

    quick_sort(alist,0,left_cur)
    quick_sort(alist,left_cur+1,end)




alist =	[1,1,4,6,3,2,5,7]
# alist =	[1,2,1,5]

# alist = list(range(10000))
quick_sort(alist,0,len(alist)-1)
print(alist)





